#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
TODO 扩展： lc647回文子串、lc5最长回文子串、lc516最长回文子序列


来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */


int maxV=0;
string rets="";

//先利用双指针解决一下吧 TODO 我擦我发现我不会写
// 由中间向两边扩散
//不需要判断回文 只对边边的元素就行
void longestPalindrome_extend(string& s,int low ,int high,int sizer) {

    if (high>sizer ||low<0)
        return ;

    while (low<=high &&low>=0 &&high<=sizer ){
        int temp=(high-low+1);
        if (s[low]==s[high])
        {
            if (temp>maxV){
                rets=s.substr(low,temp);
                maxV=temp;
            }

            low--;
            high++;
        } else
            break;

    }


}


//"babad" dp 来解决
string longestPalindrome(string s) {

    int sizer=s.size()-1;

    for (int i = 0; i <s.size() ; ++i) {
        longestPalindrome_extend(s,i,i,sizer);
        longestPalindrome_extend(s,i,i+1,sizer);
    }

    return rets;

}
//////////////////////////////////////////dp
/*
 *
 *
 *
 *动规五部曲：

确定dp数组（dp table）以及下标的含义
布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

确定递推公式
在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
以上三种情况分析完了，那么递归公式如下：

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        dp[i][j] = true;
    }
}
注意这里我没有列出当s[i]与s[j]不相等的时候，因为在下面dp[i][j]初始化的时候，就初始为false。

在得到[i,j]区间是否是回文子串的时候，直接保存最长回文子串的左边界和右边界，代码如下：

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        dp[i][j] = true;
    }
}
if (dp[i][j] && j - i + 1 > maxlenth) {
    maxlenth = j - i + 1;
    left = i;
    right = j;
}
dp数组如何初始化
dp[i][j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。

所以dp[i][j]初始化为false。

确定遍历顺序
遍历顺序可有有点讲究了。

首先从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：
 *
 *
 * */


//第二个用到了第一个  dp[i + 1][j - 1] 用到了右边的东西 因此要从右边开始遍历
string longestPalindrome(string s) {
    vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
    int maxlenth = 0;
    int left = 0;
    int right = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        for (int j = i; j < s.size(); j++) {
            if (s[i] == s[j]) {
                if (j - i <= 1) { // 情况一 和 情况二
                    dp[i][j] = true;
                } else if (dp[i + 1][j - 1]) { // 情况三
                    dp[i][j] = true;
                }
            }
            if (dp[i][j] && j - i + 1 > maxlenth) {
                maxlenth = j - i + 1;
                left = i;
                right = j;
            }
        }

    }
    return s.substr(left, right - left + 1);
}